#include "common.h"

vector<vector<int>> ans;
vector<int> ttt;
int tat;
void dfs(vector<int>& nums, int path, int index)
{
	if (path == tat)
	{
		ans.push_back(ttt);
		return;
	}
	if (path > tat)
	{
		return;
	}
	for (int i = index; i < nums.size(); i++)
	{
		ttt.push_back(nums[i]);
		dfs(nums, path + nums[i], i);
		ttt.pop_back();
	}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target)
{
	tat = target;
	dfs(candidates, 0, 0);
	return ans;
}